package com.gkj.gulimall.product.javabase;

import java.util.*;

/*class Person{
    private String  username;
    private int age;

    public String getUsername() {
        return this.username;
    }

    public void setUsername(String username) {
        this.username = username;
    }

    public int getAge() {
        return this.age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}
 class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }*/

public class LeetCode {
    /**
     * 两数之和 day1
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                arr[0] = map.get(nums[i]);
                arr[1] = i;
                break;
            }
            map.put(target - nums[i], i);
        }
        return nums;
    }

    /**
     * 有效的括号 --Leetcode Hot100
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        //解法2 借助栈的特性解决
        Stack<Character> stack = new Stack();
        if (s.length() == 1) {
            return true;
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{') {
                stack.push('}');
            } else if (s.charAt(i) == '[') {
                stack.push(']');
            } else if (s.charAt(i) == '(') {
                stack.push(')');
            } else if (stack.isEmpty() || s.charAt(i) != stack.pop()) {
                return false;
            }
        }
        //解法1
        int length = s.length() / 2;
        for (int i = 0; i < length; i++) {
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");
        }
        System.out.println(s);
        return s.length() == 0;
    }

    /**
     * 从尾到头打印链表
     *
     * @param head
     * @return
     */
    public int[] reversePrint(ListNode head) {
        int count = 0;//保存链表长度的变量
        ListNode node = head;//临时存放链表对象
        while (node != null) {
            count++;//计算有几个链表节点
            node = node.next;
        }
        int[] arr = new int[count];//声明存放链表对象值的数组
        node = head;//重置node对象
        for (int i = count - 1; i >= 0; --i) {//遍历链表取值
            //arr[4] = 1  arr[3] = 2 .... arr[0] = 5;
            arr[i] = node.val;
            node = node.next;
        }
        return arr;
//        int count = 0;int cnt = 0;
//        while(head != null){
//            count++;
//            head = head.next;
//        }
//        int[] arr = new int[count];
//        ListNode cur = null;
//        while(head != null){
//            ListNode temp = head;
//            head = head.next;
//            head.next = temp;
//            arr[cnt] = head.val;
//            cnt++;
//            head = head.next;
//        }
//        return arr;
//        int[] linkedList = {};
//        ListNode next = null;
//        int i = 0;
//        while(head.next != null){
//            ListNode temp = head.next;
//            next = head.next;
//            head = temp;
//            head.next = head;
//            linkedList[i] = head.val;
//            i++;
//        }
//        return linkedList;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode node = head;
        List<Integer> list = new ArrayList();
        while (node != null) {
            list.add(node.val);
            node = node.next;
        }
        /*ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;*/
        //构建链表
        if (list.size() == 0 || list == null) {//判断是否有链表节点元素，防止空指针
            return null;
        }
        //创建第一个链表节点对象
        ListNode newList = new ListNode(list.get(list.size() - 1));
        ListNode temp = newList;//赋值给临时节点对象
        for (int i = list.size() - 2; i >= 0; --i) {
            temp.next = new ListNode(list.get(i));//当前节点对象的下一个指向节点
            temp = temp.next;//指针后移到下一个节点对象
        }
        return newList;
    }

    /**
     * 替换空格
     *
     * @param s
     * @return
     */
    public String replaceSpace(String s) {
        //解法1 直接库函数解决
       /* String all = "";
        if(s.contains(" ")){
            all = s.replaceAll(" ", "%20");
        }
        return all; */
        //解法2 遍历字符串找空格进行替换
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (str.charAt(i) == ' ') {
                str.append("%20");//空格替换%20
            } else {
                str.append(s.charAt(i));
            }
        }
        return str.toString();
    }

    /**
     * 合并有序链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> mergeList = new ArrayList();
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {//第一个链表为空直接返回第二个链表
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        while (list1 != null) {
            mergeList.add(list1.val);
            list1 = list1.next;
        }
        while (list2 != null) {
            mergeList.add(list2.val);
            list2 = list2.next;
        }
        Collections.sort(mergeList);//排序
        ListNode mergeNode = new ListNode(mergeList.get(0));//创建第一个链表节点头
        ListNode temp = mergeNode;
        for (int i = 1; i < mergeList.size(); i++) {
            temp.next = new ListNode(mergeList.get(i));
            temp = temp.next;
        }
        return mergeNode;
    }

    /**
     * 左旋转字符串
     *
     * @param s
     * @param n
     * @return
     */
    public String reverseLeftWords(String s, int n) {
        /**    字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
         请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，
         该函数将返回左旋转两位得到的结果"cdefgab"。*/
        if ("".equals(s)) {
            return "";
        }
        StringBuilder str = new StringBuilder();
        String substring = s.substring(n);//字符串截取
        int len = s.length() - substring.length();//计算截取完的字符串前面部份
        str.append(substring);//追加截取出来的后半部分字符串
        for (int i = 0; i < len; i++) {
            str.append(s.charAt(i));
        }
        return str.toString();
    }

    /**
     * 前提：升序
     * 统计一个数字在排序数组中出现的次数
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                cnt++;
            }
        }
        return cnt;
    }

    /**
     * 数组1 - n-1中缺失的数字
     *
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        /*
        一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
        在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
        */
        int min = nums[0];
        int max = nums[nums.length - 1];
        int res = -1;
        int sum = 0;
        if (nums.length == 1) {
            return nums[0] == 1 ? 0 : 1;
        }
        for (int i = 0; i < nums.length; i++) {//求数组的总和
            sum += nums[i];
        }

//        for(int i = 1;i < nums.length;i++){
//            if(min > nums[i]){
//                min = nums[i];
//            }
//            if(max < nums[i]){
//                max = nums[i];
//            }
//        }
//        for(int i = min;i <= max;i++){
//            if(nums[i] != i){ 
//                return i;
//            }
//        }
//        return nums.length;
        return (max * (max + 1) / 2) - sum;
    }

    /**
     * 第一个只出现一次的字符
     *
     * @param s
     * @return
     */
    public char firstUniqChar(String s) {
        //abaccdeff
//        Set<Character> uniqueSet = new HashSet();
        return 'a';
    }

    /**
     * 查找数组中重复的数字
     *
     * @param nums
     * @return [2, 3, 1, 0, 2, 5, 3]
     */
    public int findRepeatNumber(int[] nums) {
        //解法1 : 使用哈希set的特性找出重复的数字返回
        Set<Integer> set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }

    /**
     * 查找所有数组中消失的数字
     * (超时运行)
     *
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList();
        int min = nums[0];//找最小值
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
            if (max < nums[i]) {
                max = nums[i];
            }
        }
        Arrays.sort(nums);
        Set<Integer> set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            if (set.add(nums[i])) {
                list.add(nums[i]);
            }
        }
        System.out.println("去重后的集合是:" + list);
        List<Integer> res = new ArrayList();
        if (min > 0) {
            for (int i = 1; i <= nums.length; i++) {
                if (!list.contains(i)) {
                    res.add(i);
                }
            }
        }
        if (min < 0) {
            for (int i = min; i <= max; i++) {
                if (!list.contains(i)) {
                    res.add(i);
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {

        System.out.println((double) 5000 / 31);
        System.out.println('c' - 'a');
        char c = new LeetCode().firstUniqChar("abaccdeff");
        System.out.println(c);
        Integer a = 129;
        Integer b = 129;
        System.out.println(a == b);//-128到127之间使用缓存的数字，其余创建包装类对象
        int missingNumber = new LeetCode().missingNumber(new int[]{0, 1});
        System.out.println("丢失的数字:" + missingNumber);
        int search = new LeetCode().search(new int[]{1, 2, 3}, 2);
        System.out.println("数组中重复的次数:" + search);
        int repeatNumber = new LeetCode().findRepeatNumber(new int[]{3, 1, 2, 3});
        System.out.println("重复的数字 " + repeatNumber);
        new LeetCode().findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}).stream().forEach((t) -> {
            System.out.println(t);
        });
        String str = "{[()]}";
        System.out.println(str.replace("()", "").replace("[]", ""));
        boolean valid = new LeetCode().isValid("(([]){})");
        System.out.println(valid);

//        String s = new LeetCode().replaceSpace("We are happy.");
//        System.out.println("替换后的字符串: " +s);
        String ss = "sfsfsd";
        System.out.println(ss.substring(2));
        String s = new LeetCode().reverseLeftWords("abcdef", 2);
        System.out.println("左旋后的字符串: " + s);
        List<Integer> list = Arrays.asList(2, 2, 1, 1, 4, 6);
        Collections.sort(list);
        System.out.println(list);
        Set set = new HashSet();
        System.out.println(set.add(1));
        System.out.println(set.add(1));
    }
}

/**
 * 包含min函数的栈
 */
class MinStack {
    Stack<Integer> stack;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        stack = new Stack();
    }

    public void push(int x) {
        stack.push(x);
    }

    public void pop() {
        if (!stack.empty()) {
            stack.pop();
        }
    }

    public int top() {
        int len = 0;
        if (!stack.empty()) {
            len = stack.size() - 1;
        }
        return stack.get(len);
    }

    public int min() {
        Object[] array = stack.toArray();
        Arrays.sort(array);
        int min = (int) array[0];
        return min;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(2);
        stack.push(1);
        stack.push(5);
        int len = stack.size() - 1;
//        System.out.println(stack.get(len));
        Object[] objects = stack.toArray();
        Arrays.sort(objects);
        int mi = (int) objects[0];
        System.out.println(mi);
    }
}

/**
 * 两个栈模拟队列
 */
class CQueue {
    Stack<Integer> stack1 = new Stack();
    Stack<Integer> stack2 = new Stack<Integer>();

    public CQueue() {
        stack1 = new Stack();//初始化栈结构
        stack2 = new Stack();
    }

    public void appendTail(int value) {
        stack1.push(value);//压栈
    }

    public int deleteHead() {
        int first = -1;
        if (stack1.isEmpty()) {
            return first;
        }
        //获取栈的第一个入栈元素
        first = stack1.get(0);
        stack2.push(first);
        stack1.removeElement(first);//移除头元素
        return stack2.pop();
    }

    public static void main(String[] args) {
        CQueue cQueue = new CQueue();
        cQueue.appendTail(1);
        cQueue.appendTail(2);
        cQueue.appendTail(3);
        int head = cQueue.deleteHead();
        System.out.println("头元素:" + head);
        int head2 = cQueue.deleteHead();
        System.out.println("头元素2:" + head2);
    }
}
